public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
//        int[] arr = new int[]{1,1,2,2,9,7,7,8,8,6,3,6,3,11};
//        for(int e: s.singleNumber(arr)) {
//            System.out.print(e + " ");
//        }
        int[] arr = new int[]{2,3};
        for(int e: s.missingTwo(arr)) {
            System.out.print(e + " ");
        }
    }

    public int[] singleNumber(int[] nums) {
        /**
         * 只出现一次的数字Ⅲ
         *  本质：
         *      在一个整数数组中恰好有两个元素只出现一次，其余所有元素均出现两次，需要我们在不使用额外数据结构的情况下找到两个只出现一次的元素
         *  思路：
         *      1，由于除目标元素外，其余所有元素均出现两次，故我们将所有元素异或，最终结果就是目标元素的异或值（异或消消乐）
         *      2，由题可知，两个目标元素均只出现一次，故其必定不相等（若是相等就不止出现一次）
         *      3，综上，我们可以得到两个目标元素的异或值，并且知道可知这个元素一定不相等
         *      4，由按位异或的特性可知，相同为0，不同为1，我们只需找出不同的比特位，并以此为依据进行分组，如此两个单独的元素一定会被分开
         *          此时这两组的最终结果就是仅出现一次的元素（这个思路在位运算中非常常见）*/
        // 1 预处理
        int n = nums.length;

        // 2 获取所有元素异或结果（也就是仅出现一次元素的异或结果）
        int firstAnswer = nums[0];
        for(int i = 1; i < n; i++) {
            firstAnswer ^= nums[i];
        }

        // 3 找到最终结果最右边第一个1作为基准点
        int lowBit = firstAnswer & (-firstAnswer);

        // 4 分组异或寻找目标值
        int x1 = 1;
        int x2 = 1;
        for(int e: nums) {
            if((e & lowBit) == 0) {
                x1 ^= e;
            } else {
                x2 ^= e;
            }
        }
        x1 ^= 1;
        x2 ^= 1;

        // 5 返回值
        return new int[]{x1, x2};
    }

    public int[] missingTwo(int[] nums) {
        /**
         * 消失的两个数字
         *  要求：
         *      在1~n所有整数中缺失了两个数字，需要在O(n)的时间复杂度和O(1)的空间复杂度找到
         *      也就是说，不能使用额外的数据结构
         *  思路：
         *      1，异或1~n 再 异或所有元素，得到两个缺失值的异或值
         *      2，在异或值中找到相异bit位作为划分依据，对1~n 和 nums数组进行分组
         *      3，对每组值进行异或，最终值就是缺失值*/
        // 1 预处理
        int n = nums.length;

        // 2 求缺失值的异或值
        int missVal = nums[0];
        for(int i = 1; i < n; i++) {
            missVal ^= nums[i];
        }
        for(int i = 1; i <= n+2; i++) {
            missVal ^= i;
        }

        // 3 找到分组划分依据（相异bit位-lowBit操作）
        int lowBit = missVal & (-missVal);

        // 4 分组并分别异或
        int x1 = 1;
        int x2 = 1;
        for(int e: nums) {
            if((e & lowBit) == 0) {
                x1 ^= e;
            } else {
                x2 ^= e;
            }
        }
        for(int i = 1; i <= n+2; i++) {
            if((i & lowBit) == 0) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        x1 ^= 1;
        x2 ^= 1;

        // 5 返回值
        return new int[]{x1, x2};
    }
}
